package org.laizili.solution.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/duplicate-zeros/">1089. 复写零</a>
 * <p>
 * tags: 栈思想；双指针
 */
public class Problem1089 {

    // 官方题解方法
    // submitted: 2022年6月17日11:44:40
    private static class Solution {
        public void duplicateZeros(int[] arr) {
            int top = 0;
            int i = -1;
            int len = arr.length;
            while (top < len) {
                ++i;
                if (arr[i] == 0) {
                    top += 2;
                } else {
                    ++top;
                }
            }
            int k = len - 1;
            // notes: 栈指针指向 len+1 的情况下
            //        原数组中缺少一个位置复制0，根据题意，要丢弃复制的零
            if (top == len + 1) {
                arr[k] = 0;
                --i;
                --k;
            }
            while (k >= 0) {
                arr[k] = arr[i];
                if (arr[i] == 0) {
                    arr[--k] = arr[i];
                }
                --i;
                --k;
            }
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ints = {0, 1, 0};
        solution.duplicateZeros(ints);
        System.out.println(Arrays.toString(ints));

        ints = new int[]{1, 0, 1, 0};
        solution.duplicateZeros(ints);
        System.out.println(Arrays.toString(ints));
    }
}
